#include "KMP.h"
#include <iostream>

using namespace std;

void KMP::match()
{
    unsigned int i,j=0;
    unsigned int len = original.length();
    getNext();
    cout<<"original: "<<original<<endl;
    cout<<"pattern : "<<pattern<<endl;
    for(i=1;i<len;++i)
    {
        while(j>0 && original[i]!=pattern[j])
            j = next[j];
        if(original[i] == pattern[j])
            ++j;
        if(j == pattern.length())
        {
            cout<<"i: "<<i<<" j: "<<j<<endl;
            cout<<"find at position "<<(i-j+1)<<endl;
            cout<<original.substr(i-j+1,j)<<endl; //从i-j+1开始，j个
            j = next[j]; //完成一次匹配之后，j已经到尽头，让j回退一步
        }
    }
    delete[] next;
    next = NULL;
}

void KMP::getNext()
{
    int i,j=0;
    int len=pattern.length();
    next[0]=next[1]=0;

    for(i=1;i<len;++i)
    {
        while(j>0 && pattern[i]!=pattern[j])
            j=next[j];
        if(pattern[i]==pattern[j])
            ++j; //如果相同，j后移
        next[i+1]=j; //此处i+1代表个数
    }
}
